1. Field of the Invention
The present invention relates to an image processing system, and more particularly, to a method, apparatus and computer program product for compressing and decompressing image data.
2. Discussion of the Background
Japanese Patent Laid-Open Publications Nos. 10-084484, 11-168633, and 11-266162 describe compression and decompression of image data by a combination of two-dimensional reversible wavelet transform processing, context model processing, and binary entropy encoding/decoding processing. Such compression and decompression devices and those according to the present invention generally include five processing blocks, as shown in FIG. 1. These processing blocks include, for example, a two-dimensional reversible wavelet transform section 10, a context model section 20, a binary entropy encoder/decoder 30, and an integration order generation section 50 perform compression and decompression of image data. For example, a FSM (Finite State Machine) coder based on a finite state machine is used as the binary entropy encoder/decoder 30.
The operation of such compression and decompression devices will now be explained. It is assumed that each device divides one component image (e.g., one of a Red, Green and Blue image) into tiles, and performs tile-by-tile image processing. First, the operation of the device in encoding (i.e., compressing) image data will be described. Based on an order transformation, performed by the two-dimensional reversible wavelet transform section 10, image data of one tile is spatially divided into frequency bands, for example, as shown in FIGS. 2A-2D, and coefficient data of each frequency band is provided to the context model section 20. Because a low frequency band is recursively spatially divided, coefficient data of each frequency band shown in FIG. 2D is obtained when image data is transformed into three levels.
In the integration order generation section 50, a bit to be encoded (hereinafter referred to as a target bit) is determined based on order of alignment information (i.e., information which indicates the order of encoding) designated by a user. In the context model section 20, context data is created based on the state of the bits (i.e., each bit of a context template shown in FIG. 3) around the target bit, and the binary entropy encoder/decoder 30 receives the generated context data.
In the binary entropy encoder/decoder 30, the target bit is encoded using probability estimation based on the context data and the target bit so as to generate a code word. Then, a code stream of one tile is output after tag information, including a compression condition, has been added to a header of the code word via a tag processing section 40.
In a wavelet transform, coefficient data, corresponding only to the coefficient data of a high frequency band (DS, SD, DD) shown via shading in FIG. 2B, 2C and 2D, is encoded. Then, the coefficient data of a low frequency band (SS) is output without encoding into a code stream. In a three-level wavelet transformation, the coefficient data of a high frequency band shown via shading in FIG. 2D is encoded, and the coefficient data of a low frequency band (SS3) is not encoded.
Decoding is performed via a method similar to the above-described encoding method. In addition, the encoding and decoding of the coefficient data is performed from the most significant bit data to the least significant bit data, at every bit plane.
In a decompression (i.e., decoding) process, image data of one tile is created from a code stream of one tile and is the reverse of a compression (i.e., encoding) process. In this case, a target bit position is determined in an integration order generation section 50, based on tag information at the header of a codestream. Then, context data is created in the context model section 20 based on a state of the bits (i.e., which have already been encoded) around the target bit.
In the binary entropy encoder/decoder 30, decoding is performed using probability estimation based on the context data and the codestream, and the decoded bit is output. The decoded bit is written into a target bit position of a buffer in the context model section 20. Thus, coefficient data of each frequency band is restored. The coefficient data is reverse transformed by the two-dimensional reversible wavelet transform section 10, and image data of one tile is reconstructed.
The tag processing section 40 adds tag information to a compressed codestream and interprets the tag information added to the codestream. In a compression (i.e., encoding) process, the tag processing section 40 combines a plurality of components formed in one tile in a predetermined order, so as to generate one codestream. The tag processing section 40 then adds tag information to the header of the codestream. In a decompression (i.e., decoding) process, the tag processing section 40 interprets tag information and resolves one codestream into a plurality of components in one tile.
In such devices as described above, wavelet transformed coefficient data is encoded with a bit-significance representation, as shown in FIG. 4. Generally, in xe2x80x9c2""s complementxe2x80x9d and xe2x80x9csign+ magnitudexe2x80x9d representations, the sign is represented by the uppermost bit. In contrast, in a bit-significance representation, an absolute value of a coefficient value is examined from an upper bit to a lower bit to determine the first logic xe2x80x9c1xe2x80x9d bit (e.g., referred to as a xe2x80x9c1xe2x80x9d head bit). The sign bit is encoded right after the encoding of the xe2x80x9c1xe2x80x9d head bit. Bits having logic values of xe2x80x9c0xe2x80x9d and located at higher bit positions than the xe2x80x9c1xe2x80x9d header bit are referred to as xe2x80x9c0xe2x80x9d header bits. Bits having logic values of xe2x80x9c0xe2x80x9d or xe2x80x9c1xe2x80x9d and located at lower bit positions than the xe2x80x9c1xe2x80x9d head bit are referred to as tail bits.
Referring to FIG. 5, a bit from each high frequency band (i.e., one of DS, SD, and DD) is examined with respect to a coefficient word of a pixel (i.e., in a depth direction) from MSB (the most significant bit) to LSB (the least significant bit). When the xe2x80x9c1xe2x80x9d head bit (i.e., the bit circled in FIG. 5) is a target bit, a sign bit S of the coefficient word is encoded (or decoded), immediately after the xe2x80x9c1xe2x80x9d head bit is encoded (or decoded). Then, a bit in the next target position is encoded (or decoded). When a target bit is a bit (i.e., including tail bits) other than the xe2x80x9c1xe2x80x9d head bit, the next target bit is encoded (or decoded) instead of the sign bit S, after the target bit has been encoded (or decoded). Namely, a sign bit is encoded (or decode) together with the xe2x80x9c1xe2x80x9d head bit.
As described above, encoding (or decoding) of each high frequency band is performed in order of significant bits at every bit plane. However, a target bit moves in the order as shown in FIG. 6 in each bit plane. Accordingly, the target bit moves in a zigzag order of T0, T1, T2, and T3 in a left most 2xc3x972 pixel region. Then, the target bit moves in a zigzag order of T4, T5, T6, and T7 in the next 2xc3x972 pixel region. This process is repeated until all the bits are encoded (or decoded).
Such devices as discussed above, generally, are implemented via specific hardware, when processing speed higher than that of an implementation using software and a personal computer or workstation is required. In addition, dataflow in the context model section 20 and between the context model section 20 and the binary entropy encoder/decoder 30 is arranged in series, as shown in FIGS. 7 and 8. Further, the context model section 20 and the binary entropy encoder/decoder 30 are serially operated as shown in FIG. 9A.
In such devices, processing time required for compression and decompression is determined by multiplying a basic cycle time by the number of processing cycles. However, the shortening of the basic cycle time is limited because the processing is performed in series, as described above. In addition, in contrast to the encoding operation, because a decoded bit is used as a context template in a decoding operation, a feedback loop, shown as a dotted line in FIG. 8, is required, which makes it difficult to shorten the basic cycle time.
In order to shorten a processing time required for compression and decompression, two or more sets of the context model section 20 and the two-element entropy encoder/decoder 30 might be employed so as to operate them in parallel. However, simply operating such device in parallel typically cannot reduce the number of processing cycles, resulting in deterioration of compression efficiency.
The present invention has been made in view of the above and other problems and addresses the same.
The present invention advantageously provides a novel compression and decompression apparatus, method and computer program product, wherein compression and decompression of image data is performed via a combination of two-dimensional reversible wavelet transform processing, context model processing, and binary entropy encode/decode processing. Faster processing, as compared to conventional devices and methods, is achieved according to the present invention by performing the context model processing and the binary entropy encoding/decoding processing in parallel, such that two-story pipeline processing is performed, resulting in a reduction of a basic cycle time.